//
// Created by mac on 2023/11/2.
//

// #include <iostream>
// #include <algorithm>
// #include <vector>
// using namespace std;

// int main()
// {
//     // 1、数据输入
//     int n = 0; // 物品个数
//     int V = 0; // 背包容量
//     cin >> n >> V;
//     // n 个物品的体积和价值表，其中第0个位置表示一个虚拟物品
//     // 它的体积和价值都为0，设置它的目的是为了下标和dp表对应
//     vector<int> v(n + 1), w(n + 1);

//     for(int i = 1; i <= n; ++i)
//         cin >> v[i] >> w[i];

//     // 2、创建 dp 表
//     vector<int> dp(V + 1);

//     // 3、解决第一问
//     for(int i = 1; i <= n; ++i)
//         for(int j = V; j - v[i] >= 0; --j)
//             dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
//     cout << dp[V] << endl;

//     // 4、解决第二问
//     for(int j = 1; j <= V; ++j) dp[j] = -1;

//     for(int i = 1; i <= n; ++i)
//         for(int j = V; j - v[i] >= 0; --j)
//         {
//             if(dp[j - v[i]] != -1) dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
//         }
//     cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

//     return 0;
// }

/*
- 时间复杂度：O(nV)
- 空间复杂度：O(V)
*/














// #include <iostream>
// #include <algorithm>
// #include <vector>
// using namespace std;

// int main()
// {
//     // 1、数据输入
//     int n = 0; // 物品个数
//     int V = 0; // 背包容量
//     cin >> n >> V;
//     // n 个物品的体积和价值表，其中第0个位置表示一个虚拟物品
//     // 它的体积和价值都为0，设置它的目的是为了下标和dp表对应
//     vector<int> v(n + 1), w(n + 1);

//     for(int i = 1; i <= n; ++i)
//         cin >> v[i] >> w[i];

//     // 2、创建 dp 表
//     vector<vector<int>> dp(n + 1, vector<int>(V + 1));

//     // 3、解决第一问
//     for(int i = 1; i <= n; ++i)
//         for(int j = 1; j <= V; ++j)
//         {
//             dp[i][j] = dp[i - 1][j];
//             if(j - v[i] >= 0) dp[i][j] = max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
//         }
//     cout << dp[n][V] << endl;

//     // 4、解决第二问
//     for(int j = 1; j <= V; ++j) dp[0][j] = -1;

//     for(int i = 1; i <= n; ++i)
//         for(int j = 1; j <= V; ++j)
//         {
//             dp[i][j] = dp[i - 1][j];
//             if(j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) dp[i][j] = max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
//         }
//     cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

//     return 0;
// }

// /*
// - 时间复杂度：O(nV)
// - 空间复杂度：O(nV)
// */












